package offer;

import binaryTree.basic.TreeNode;
import sun.awt.image.ImageWatched;
import sun.plugin.javascript.navig.Link;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Offer34 {
    ArrayList path;
    ArrayList<ArrayList<Integer>> res;
    int curSum = 0;

    public ArrayList<ArrayList<Integer>> findPath(TreeNode root, int target) {
        path = new ArrayList<TreeNode>();
        res = new ArrayList<>();
        if (root == null) {
            return null;
        }
        dfs(root, target, curSum, path);
        return res;
    }

    public void dfs(TreeNode root, int target, int curSum, ArrayList path) {

        if (root == null || curSum > target) {
            return;
        }
        path.add(root);
        curSum += root.val;
        if (curSum == target && root.left == null && root.right == null) {
            res.add(path);
        }
        dfs(root.left, target, curSum, path);
        dfs(root.right, target, curSum, path);
        path.remove(path.size() - 1);
        curSum -= root.val;
    }

    public static void main(String[] args) {
        Offer34 offer34 = new Offer34();
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(1);
        TreeNode treeNode4 = new TreeNode(1);
        TreeNode treeNode5 = new TreeNode(1);
        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        ArrayList<ArrayList<Integer>> path = offer34.findPath(treeNode1, 3);
        for (ArrayList<Integer>  a: path) {
            System.out.println(a.toArray());
        }
    }


}